{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Squirrel Simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #松鼠模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现在有一棵树，一只松鼠和一些坚果。位置由二维网格的单元格表示。你的目标是找到松鼠收集所有坚果的<strong>最小路程</strong>，且坚果是一颗接一颗地被放在树下。松鼠一次最多只能携带<strong>一颗</strong>坚果，松鼠可以向上，向下，向左和向右四个方向移动到相邻的单元格。移动次数表示路程。</p>\n",
    "\n",
    "<p><strong>输入 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> \n",
    "高度 : 5\n",
    "宽度 : 7\n",
    "树的位置 : [2,2]\n",
    "松鼠 : [4,4]\n",
    "坚果 : [[3,0], [2,5]]\n",
    "<strong>输出:</strong> 12\n",
    "<strong>解释:</strong>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2018/10/22/squirrel_simulation.png\" style=\"width: 40%;\">​​​​​\n",
    "</pre>\n",
    "\n",
    "<p><strong>注意:</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>所有给定的位置不会重叠。</li>\n",
    "\t<li>松鼠一次最多只能携带一颗坚果。</li>\n",
    "\t<li>给定的坚果位置没有顺序。</li>\n",
    "\t<li>高度和宽度是正整数。 3 &lt;= 高度 * 宽度 &lt;= 10,000。</li>\n",
    "\t<li>给定的网格至少包含一颗坚果，唯一的一棵树和一只松鼠。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [squirrel-simulation](https://leetcode.cn/problems/squirrel-simulation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [squirrel-simulation](https://leetcode.cn/problems/squirrel-simulation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n7\\n[2,2]\\n[4,4]\\n[[3,0], [2,5]]', '1\\n3\\n[0,1]\\n[0,0]\\n[[0,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "        def dis(x,i):\n",
    "            return abs(x[0]-i[0])+abs(x[1]-i[1])\n",
    "\n",
    "        res=0\n",
    "        ans=inf\n",
    "        for i,x in enumerate(nuts):\n",
    "            p=dis(x,tree)\n",
    "            ans=min(dis(squirrel,x)-p,ans)\n",
    "            res+=p*2\n",
    "        return res+ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "        def cal(p1, p2):\n",
    "            return abs(p1[0]-p2[0])+abs(p1[1]-p2[1])\n",
    "        res = 2*sum(cal(tree, p) for p in nuts)\n",
    "        return res + min(cal(squirrel, p)-cal(tree, p) for p in nuts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "        return 2 * sum(abs(nut[0] - tree[0]) + abs(nut[1] - tree[1]) for nut in nuts) + min((abs(nut[0] - squirrel[0]) + abs(nut[1] - squirrel[1])) - (abs(nut[0] - tree[0]) + abs(nut[1] - tree[1])) for nut in nuts)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "\n",
    "        #### 先不管squirrel，先计算tree到每个nut的来回路程的总和\n",
    "\n",
    "        total_sum = 0;\n",
    "\n",
    "        for x,y in nuts:\n",
    "\n",
    "            dist_tree_nut = abs(tree[0] - x) + abs(tree[1] - y)\n",
    "\n",
    "            total_sum += 2 * dist_tree_nut\n",
    "\n",
    "        \n",
    "\n",
    "        #### 再考虑松鼠 （其实也可以在上面一起，但是怕思路不清晰，分批次考虑，复杂度也没有升级）\n",
    "\n",
    "        res = float('inf')\n",
    "\n",
    "        for x,y in nuts:\n",
    "\n",
    "            dist_tree_nut = abs(tree[0] - x) + abs(tree[1] - y)\n",
    "\n",
    "            dist_squirrel_nut = abs(squirrel[0] - x) + abs(squirrel[1] - y)\n",
    "\n",
    "            cur = total_sum - dist_tree_nut + dist_squirrel_nut\n",
    "\n",
    "            res = min(res, cur)\n",
    "\n",
    "\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "        tot = 0\n",
    "        tx, ty = tree\n",
    "        for x, y in nuts:\n",
    "            tot += abs(x - tx) + abs(y - ty)\n",
    "        tot *= 2\n",
    "        ans = inf\n",
    "        sx, sy = squirrel\n",
    "        for x, y in nuts:\n",
    "            ans = min(ans, tot - (abs(x - tx) + abs(y - ty)) + \n",
    "            abs(sx - x) + abs(sy - y))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "        dist = 0\n",
    "        for nut in nuts:\n",
    "            dist += 2*(abs(tree[0] - nut[0]) + abs(tree[1] - nut[1]))\n",
    "        \n",
    "        mdist = float('inf')\n",
    "        for nut in nuts:\n",
    "            dt = abs(tree[0] - nut[0]) + abs(tree[1] - nut[1]) \n",
    "            ds = abs(squirrel[0] - nut[0]) + abs(squirrel[1] - nut[1])\n",
    "            if (t := dist - dt + ds) < mdist:\n",
    "                mdist = t\n",
    "        \n",
    "        return mdist\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "        tot = 0\n",
    "        tx, ty = tree\n",
    "        for nx, ny in nuts:\n",
    "            tot += 2 * (abs(nx - tx) + abs(ny - ty)) \n",
    "        sx, sy = squirrel\n",
    "        ans = inf\n",
    "        for nx, ny in nuts:\n",
    "            d = tot - abs(nx - tx) - abs(ny - ty) + abs(nx - sx) + abs(ny - sy)\n",
    "            ans = min(ans, d)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistance(self, a, b):\n",
    "        return abs(a[0] - b[0]) + abs(a[1] - b[1])\n",
    "\n",
    "    def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "        ans = int(1e9)\n",
    "        sum_dis = sum(self.getDistance(nut, tree) for nut in nuts) * 2\n",
    "        for first_nut in nuts:\n",
    "            cur = sum_dis - self.getDistance(first_nut, tree) + self.getDistance(first_nut, squirrel)\n",
    "            ans = min(cur, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "        total_sum = 0;\n",
    "        for x,y in nuts:\n",
    "            dist_tree_nut = abs(tree[0] - x) + abs(tree[1] - y)\n",
    "            total_sum += 2 * dist_tree_nut\n",
    "\n",
    "        res = float('inf')\n",
    "        for x,y in nuts:\n",
    "            dist_tree_nut = abs(tree[0] - x) + abs(tree[1] - y)\n",
    "            dist_squirrel_nut = abs(squirrel[0] - x) + abs(squirrel[1] - y)\n",
    "            cur = total_sum - dist_tree_nut + dist_squirrel_nut\n",
    "            res = min(res, cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calDistance(self, coord1, coord2):\n",
    "        return abs(coord1[0] - coord2[0]) + abs(coord1[1] -  coord2[1])\n",
    "\n",
    "\n",
    "\n",
    "    def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "        if len(nuts) == 0:\n",
    "            return 0\n",
    "        cur_max = self.calDistance(nuts[0], tree) - self.calDistance(nuts[0], squirrel)\n",
    "        res = 2 * self.calDistance(nuts[0], tree)\n",
    "        for i in range(len(nuts)):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            temp = self.calDistance(nuts[i], tree) - self.calDistance(nuts[i], squirrel)\n",
    "            if temp > cur_max:\n",
    "                cur_max = temp\n",
    "            res += 2 * self.calDistance(nuts[i], tree)\n",
    "        return res - cur_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "        box1 = []\n",
    "        box2 = []\n",
    "        for i in nuts:\n",
    "            box1.append(abs(i[0]-tree[0]) +abs(i[1]-tree[1]))\n",
    "            box2.append(abs(i[0]-squirrel[0])+abs(i[1]-squirrel[1]))\n",
    "        length = len(box1)\n",
    "        ans = sum(box1)*10\n",
    "        sumN = sum(box1)\n",
    "        for i in range(length):\n",
    "            ans = min(ans,2*sumN-box1[i]+box2[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, m: int, n: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "        dp=[[-1]*n for _ in range(m)]\n",
    "        q=[tree]\n",
    "        dp[tree[0]][tree[1]]=0\n",
    "        while q:\n",
    "            q,nq=[],q\n",
    "            for x,y in nq:\n",
    "                t=dp[x][y]\n",
    "                for nx,ny in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "                    if 0<=nx<m and 0<=ny<n and dp[nx][ny]==-1:\n",
    "                        dp[nx][ny]=t+1\n",
    "                        q.append([nx,ny])\n",
    "        sdp=[[-1]*n for _ in range(m)]\n",
    "        sdp[squirrel[0]][squirrel[1]]=0\n",
    "        q=[squirrel]\n",
    "        while q:\n",
    "            q,nq=[],q\n",
    "            for x,y in nq:\n",
    "                t=sdp[x][y]\n",
    "                for nx,ny in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "                    if 0<=nx<m and 0<=ny<n and sdp[nx][ny]==-1:\n",
    "                        sdp[nx][ny]=t+1\n",
    "                        q.append([nx,ny])\n",
    "        res=0\n",
    "        xx=-100000000000\n",
    "        for x,y in nuts:\n",
    "            res+=dp[x][y]*2\n",
    "            xx=max(xx,dp[x][y]-sdp[x][y])\n",
    "        return res-xx\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistance(self, a, b):\n",
    "        return abs(a[0]-b[0]) + abs(a[1]-b[1])\n",
    "\n",
    "    def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "        res = float('inf')\n",
    "        total_dis = sum(self.getDistance(nut, tree) for nut in nuts) * 2\n",
    "        for first_nut in nuts:\n",
    "            tmp = total_dis - self.getDistance(first_nut, tree) + self.getDistance(first_nut, squirrel)\n",
    "            res = min(tmp, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDistance(self, a, b):\n",
    "        return abs(a[0] - b[0]) + abs(a[1] - b[1])\n",
    "\n",
    "    def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "        ans = int(1e9)\n",
    "        sum_dis = sum(self.getDistance(nut, tree) for nut in nuts) * 2\n",
    "        for first_nut in nuts:\n",
    "            cur = sum_dis - self.getDistance(first_nut, tree) + self.getDistance(first_nut, squirrel)\n",
    "            ans = min(cur, ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:\n",
    "        box1 = []\n",
    "        box2 = []\n",
    "        for i in nuts:\n",
    "            box1.append(abs(i[0]-tree[0]) +abs(i[1]-tree[1]))\n",
    "            box2.append(abs(i[0]-squirrel[0])+abs(i[1]-squirrel[1]))\n",
    "        length = len(box1)\n",
    "        ans = sum(box1)*10\n",
    "        sumN = sum(box1)\n",
    "        for i in range(length):\n",
    "            ans = min(ans,2*sumN-box1[i]+box2[i])\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
